class Solution(object):
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        DP = [i + 1 for i in range(n)]
        DP[0] = 0
        for i in range(1, n // 2):
            base = i
            step = i + 1
            k = 1
            while base + k * step < n:
                DP[base + k * step] = min(DP[base + k * step], DP[base] + k + 1)
                k += 1
        return DP[-1]


